package swardToOffer.method_2_sort_or_find.find;

/**
 * @Author ChanZany
 * @Date 2021/5/26 8:31
 * @Version 1.0
 * <p>
 * 面试题53（一）：数字在排序数组中出现的次数
 * 题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了3次，因此输出3。
 * <p>
 * 思路:二分查找
 * left,right初始化为0,len-1
 * 计算mid = left + (right-left)>>1
 * 当arr[mid]>target时,说明target一定在mid左边,即[left,mid-1]区间内,这时相当于将right=mid-1
 * 当arr[mid]<target时,说明target在mid右边,这时移动左指针left=mid+1,将搜索区间缩小到[mid+1,right]
 * 当arr[mid]==target时,需要查找target的所在区间即左边界和有边界.
 * 左边界在[left,mid-1],执行right=mid-1;
 * 右边界在[mid+1,right],执行left=mid+1;
 * 当 left>=right时,停止二分
 */
public class NumberOfK {

    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= target) i = m + 1; //<=时,i最终会在target的右边界+1的地方
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if (j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0;
        j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] < target) i = m + 1;
            else j = m - 1;   //这个else相当于v[mid]>=target,right=mid-1,right最终会在target的左边界-1的地方
        }
        int left = j;
        return right - left - 1;
    }

    public int search2(int[] nums, int target) {
        int len = nums.length;
        if (len <= 0) return -1;
        return helper(nums, target) - helper(nums, target - 1);
    }

    private int helper(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    public static void main(String[] args) {
        NumberOfK Main = new NumberOfK();
        int[] nums = new int[]{1, 2, 3, 3, 3, 4, 5};
        System.out.println(Main.search2(nums, 3));
    }
}
